package Sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {1,5,6,3,2,4,8,7,9,10};
        int[] arr1 = {1,5,6,3,2,4,8,7,9,10};
        quickSort1(arr1);
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arr1));
    }

    //单边循环快排要点:
    //选择最右侧元素作为基准点
    //j 找比基准点小的，i 找基准点大的，一旦找到，二者进行交换:
    //                   交换时机: j 找到小的，且与 i 不相等
    //                   i 找到 >= 基准点元素后，不应自增
    // 最后基准点与 i 交换， i 即为基准点最终索引
    public static void quickSort(int[] arr) {
        recursion(arr,0,arr.length-1);
    }
    private static void recursion(int[] arr,int left,int right) {
        if (left >= right) {
            return;
        }
        //先找到基准点
        int m = benchmark(arr,left,right);
        //切分基准点两侧
        recursion(arr, left, m - 1);
        recursion(arr, m + 1, right);

    }
    private static int benchmark(int[] arr,int left,int right) {
        int temp = arr[right];
        //i 找最大值、 j 找最小值，一旦 j 找到最小值且 j != i 就可以交换了
        int i = left;
        int j = left;
        while (j < right) {
            if (arr[j] < temp) {
                if (i != j) {
                    //交换
                    swap(arr,i,j);
                }
                i++;
            }
            j++;
        }
        swap(arr,i,right);
        return i;
    }

    private static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //双边循环快排要点:
    //选择最左侧元素作为基准点
    //j 找比基准点小的, i 找比基准点大的，一旦找到，二者进行交换
    //       i 从左向右
    //       j 从右先左
    // 最后基准点与 i 交换， i 即为基准点最终索引
    public static void quickSort1(int[] arr) {
        recursion1(arr,0,arr.length-1);
    }
    private static void recursion1(int[] arr,int left,int right) {
        if (left >= right) {
            return;
        }
        int m = benchmark2(arr,left,right);
        recursion1(arr,left,m - 1);
        recursion1(arr,m + 1,right);

    }
    private static int benchmark1(int[] arr,int left,int right) {
        int temp = arr[left];
        int i = left;
        int j = right;
        while (i < j) {
            while (i < j && temp < arr[j]) {
                j--;
            }
            while (i < j && temp >= arr[i]) {
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,left,i);
        return i;
    }

    //考虑快排时，遇到的重复元素过多而进行改良
    private static int benchmark2(int[] arr,int left,int right) {
        int temp = arr[left];
        int i = left + 1;
        int j = right;
        while(i <= j) {
            while(i <= j && arr[i] < temp) {
                i++;
            }
            while (i <= j && arr[j] > temp ) {
                j--;
            }
            if (i <= j) {
                swap(arr,i,j);
                i++;
                j--;
            }
        }
        swap(arr,left,j);
        return j;
    }


}
